<TITLE>prob005: low autocorrelation binary sequences</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob005: low autocorrelation binary sequences</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Results </H3>

With non-periodic boundary conditions,
problems have only been solved 
by exhaustive enumeration of all 
configurations. This has found ground states up to n=50. 
The ground states for n from 17 to 50 can be found at
  <a href="http://itp.nat.uni-magdeburg.de/~mertens/bernasconi/open.dat">
  http://itp.nat.uni-magdeburg.de/~mertens/bernasconi/open.dat</a>.
<P>

With periodic boundary conditions,
the situation is better. The tight
connection between the correlations of periodic binary sequences and mathematical objects
called cyclic difference sets can be exploited to get some exact 
analytical results about the states. 
The density of states for n up to 41 can be
  found at
  <a href="http://itp.nat.uni-magdeburg.de/~mertens/bernasconi/cyclic.shtml">
  http://itp.nat.uni-magdeburg.de/~mertens/bernasconi/cyclic.shtml</a>.

<P>

<P>

These problems pose a significant
challenge to local search methods. Natural
objective functions have a ``golf course'' shape,
with holes in this landscape that are extremely isolated in configuration space. 
However, Steven Prestwich <a href="labs.ps">reports</a> good results
with an hybrid algorithm. 


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


